1. Field of the Invention
The present invention relates to an apparatus for selecting a route for delivering packets in a packet-switched communications network, and more particularly, to an apparatus for selecting a route in a packet-switched communications network where a plurality of candidate routes are available between a sending node and a receiving node.
2. Description of the Related Art
In recent years, a packet-switched high-speed data communication service called "Switched Multi-megabit Data Service (SMDS)" has been developed for use in broadband networks. This connectionless data service delivers a packet to its destination according to address information written in its header field, without establishing a network connection in advance. When a plurality of intermediate routes exist between a sending node and a receiving node in such a fast packet-switched network, the system must select one of the routes which is considered to be the most suitable.
To make such a selection, conventional connectionless fast packet-switched networks execute a route selection process by using three methods #1 to #3 based on different criteria as detailed below. These three methods are prioritized and used in combination of two or more until a single best solution is reached. METHOD #1! For each candidate route that connects the sending node to the receiving node, the selection process counts the number of intermediate nodes (or relaying nodes) on the route, and chooses the best route(s) that exhibit the smallest number of relaying nodes.
METHOD #2! For each candidate route, the selection process accumulates the channel capacity of every intermediate channel (or inter-node link) running between two adjacent nodes on the route, and then chooses the route(s) that exhibit the largest total channel capacity.
METHOD #3! For identification purposes, serial node numbers are assigned beforehand to all the relaying nodes. From among the candidate routes remaining unsolved, the route selection process chooses one route that involves a relaying node with the smallest identification number.
The route selection process tries to choose a route by using the above method #1. If this attempt results in two or more candidate routes meeting the first criterion, then the selection process tries it again with the method #2. The selection process will further apply the method #3 if the method #2 failed to narrow down the candidates to one.
Take a fast packet-switched network of FIG. 24, for example. Being applied to this network, the above-described conventional selection process will yield a routing data table as shown in FIG. 25, in which all possible sender-receiver pairs and their respective best routes are summarized, together with the total channel capacity evaluated.
More specifically, the fast packet-switched network of FIG. 24 consists of six nodes named "SS-1" to "SS-6", where "SS" implies switching systems. These nodes SS-1 to SS-6 are interconnected by a plurality of internode links each having predetermined channel capacity of, say 50, 10, or 30. Think of a packet that is sent from the node SS-1 (sending node) to the node SS-3 (receiving node), for example. Apparently, there are two potential routes: one involving the node SS-2 as a relaying node and the other involving the node SS-5 as a relaying node. In this case, however, the first two selection methods #1 and #2 are unable to determine which route will provide better performance in the packet transmission. Thus, the route selection process finally chooses the route via the node SS-2, according to the node number-based third selection method #3. The routing data table shown in FIG. 25 is a summary of such a route selection process for all possible sender-receiver pairs.
The above-described conventional route selection method, however, has the following four problems:
PROBLEM #1! Assume that a fast packet-switched network shown in FIG. 26 is given, and there are two possible ways for a sending node SS-1 to reach a receiving node SS-4: a first route passing through a relaying node SS-2 and a second route passing through a relaying node SS-3. When the above-described route selection methods are applied to this case, the first route will finally be chosen, based on the identification number third selection method #3, because the selection methods #1 and #2 cannot differentiate between the two candidates.
However, the obtained route, which involves the relaying node SS-2, is not the best route at all. The reason is that this route includes a narrow channel SS-2!-SS-4 ! with capacity "10" which plays as a dominant factor to determine the overall performance of this route. That is, the packet transmission capability of this route is limited by the channel capacity "10".
As opposed to this, the other route which passes through the node SS-3 provides the minimum channel capacity of 30. That is, this second route has a greater packet transmission capability with the capacity of 30, and therefore, the route selection process should have chosen the second route to reduce the probability of traffic congestion and enable more stable packet transmission. Nevertheless, it chooses the first route without knowing the benefits of the other route.
PROBLEM #2! Assume next that another fast packet-switched network shown in FIG. 27 is given, where two routes are available for a node SS-1 to reach another node SS-3: a first route passing through a relaying node SS-2 and a second route passing through a relaying node SS-4. According to the above-described algorithm, the route selection process will choose the second route, based on the selection method #2.
However, it should be noted that the relaying node SS-2 is connected not only to the nodes SS-1 and SS-4 but also to other neighboring nodes SS-5, SS-6, and SS-7, and therefore, packets may flow into the node SS-2 from those nodes. If this point is taken into consideration, the first route passing through the relaying node SS-4 will probably allow more stable packet transmission than the first route which uses the node SS-2 as the relaying node. Nevertheless, the conventional route selection process selects the second route without thinking of the above merit of the first route.
PROBLEM #3! FIG. 28 shows still another example of a fast packet-switched network, where packets are sent from three nodes SS-5, SS-6, and SS-7 to a single node SS4 via a relaying node SS-1. There are two routes available for the relaying node SS-1 to reach the destination node SS-4: a first route passing through a relaying node SS-2 and a second route passing through a different relaying node SS-3. According to the above-described route selection algorithms, the selection methods #1 and #2 are unable to differentiate between those two candidate routes, and as a result of comparison of the node numbers, the first route will finally be chosen to provide data services for all the sending nodes SS-5, SS-6, and SS-7.
The second route will never be chosen, although it has the same channel capacity as that of the first route. This route selection will impose a greater load to the first route, while leaving the second route unused. As such, the conventional route selection algorithm has a problem in terms of effective use of routes available in the network.
PROBLEM #4! In a fast packet-switched network shown in FIG. 29, a sending node SS-1 transmits a packet to a receiving node SS-6, where two possible routes exist: a first route involving a pair of relaying nodes SS-4 and SS-5, and a second route involving another pair of relaying nodes SS-2 and SS-3. According to the conventional route selection algorithm, the selection methods #1 and #2 cannot differentiate between the two candidates. As a result of comparison of the node numbers, the second route is finally chosen.
The non-selected first route, however, is backed up by a spare channel running in parallel with the first route for the purpose of fault tolerance. This first route will provide more reliable packet transmission services than the second route. Nevertheless, the conventional route selection algorithm chooses the second route without knowing such a benefit of the first route.